import java.util.*;

/**
 * @author LKQ
 * @date 2022/3/28 9:08
 * @description 红色和蓝色边分别见图，搜索时使用数组记录【当前节点，需要使用的颜色】交替搜索
 * 0代表红色，1代表蓝色，对于颜色i，下一次的颜色为i ^ 1;
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] redEdges = {{0,1}, {0,2}}, blueEdges = {{1,0}};
        solution.shortestAlternatingPaths(3, redEdges, blueEdges);
    }

    public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
        // 红黄两条边，每条边存储每个节点可到达节点和
        List<Integer>[][] es = new List[2][n];
        for (int i = 0; i < n; i++) {
            es[0][i] = new ArrayList<>();
            es[1][i] = new ArrayList<>();
        }
        // 红色边，每个节点red[0]可到达的节点red[1]
        for (int[] red : redEdges) {
            es[0][red[0]].add(red[1]);
        }
        for (int[] blue : blueEdges) {
            es[1][blue[0]].add(blue[1]);
        }
        // 初始化结果
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        ans[0] = 0;
        Queue<int[]> q = new LinkedList<>();
        // 0开始的节点，后面代表颜色
        q.offer(new int[]{0, 0});
        q.offer(new int[]{0, 1});
        boolean[][] visited = new boolean[2][n];
        int dis = 1;
        while (!q.isEmpty()) {
            for (int i = q.size(); i > 0 ; i--) {
                int[] pos = q.poll();
                // es的pos[1]色边的pos[0]节点
                for (int next : es[pos[1]][pos[0]]) {
                    if (visited[pos[1] ^ 1][next]) {
                        // 如果不同颜色边的该节点访问过
                        continue;
                    }
                    // 访问该节点置为true
                    visited[pos[1] ^ 1][next] = true;
                    if (ans[next] == -1) {
                        ans[next] = dis;
                    }
                    q.offer(new int[]{next, pos[1] ^ 1});
                }
            }
            dis++;
        }
        return ans;
    }
}
